package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 * b
 * arr
 * https://leetcode.cn/contest/ubiquant2022/problems/uGuf0v/
 * 九坤-03. 数字默契考验
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/10 17:20
 */
public class MinOperations03 {

    public int minOperations(int[] numbers) {
        int item = numbers[0];
        for (int number : numbers) {
            item = gcd(item, number);
        }
        int length = numbers.length;
        long v = numbers[0] / item;
        for (int i = 0; i < length; i++) {
            int t = numbers[i] / item;
            if (!check(t)) {
                return -1;
            }
            numbers[i] = t;
            v = (v / gcd(v, t) * t);
        }
        int count = 0;
        for (int number : numbers) {
            count += getCount(v / number);
        }
        return count;
    }

    private int getCount(long num) {
        int c = 0;
        while ((num & 1) == 0) {
            c++;
            num >>= 1;
        }
        while (num % 3 == 0) {
            c++;
            num /= 3;
        }
        return c;
    }

    private boolean check(int num) {
        while ((num & 1) == 0) {
            num >>= 1;
        }
        while (num % 3 == 0) {
            num /= 3;
        }
        return num == 1;
    }

    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    private long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

}
